1. 题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1: 输入: 4 输出: 2

示例 2: 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sqrtx 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题思路

1、公式法：

「袖珍计算器算法」是一种用指数函数 $\exp$ 和对数函数 $ln$ 代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。

$$\sqrt{x}=x^{\frac{1}{2}}=(e^{ln\ x})^{\frac{1}{2}}=e^{\frac{1}{2}\ ln\ x}$$

需要验算。

2、二分查找。

3、还可以用牛顿迭代，数学渣不看。

3. 代码

3.1. 公式法

class Solution {
public:
    int mySqrt(int x) {
         if (x == 0) {
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};

3.2. 二分

class Solution {
public:
    int mySqrt(int x) {
        long long l=-1,r=(long long)x+1;
        while(l+1!=r){
            long long mid=(l+r)>>1;
            if(mid*mid<=x) l=mid;
            else  r=mid; 
        }
        return l;
    }
};

class Solution {
public:
    int mySqrt(int x) {
        long long l = 0, r = x;
        while (l < r) {
            long long mid = (long long )(r + l +1 ) / 2;
            if (mid*mid <= x) {
                l=mid;
            }else {
                r = mid - 1;
            }
        }
        return l;
    }
};